◀ Prev · Parts · Full · Next ▶

• The class RAND is a Σ Σ 2 0 {\displaystyle \Sigma _{2}^{0}} subset of Cantor space, where Σ Σ 2 0 {\displaystyle \Sigma _{2}^{0}} refers to the second level of the arithmetical hierarchy. This is because a sequence S is in RAND if and only if there is some open set in the universal effective null cover that does not contain S; this property can be seen to be definable by a Σ Σ 2 0 {\displaystyle \Sigma _{2}^{0}} formula.

• There is a random sequence which is Δ Δ 2 0 {\displaystyle \Delta _{2}^{0}} , that is, computable relative to an oracle for the Halting problem. (Schnorr 1971) Chaitin's Ω is an example of such a sequence.

• No random sequence is decidable, computably enumerable, or co-computably-enumerable. Since these correspond to the Δ Δ 1 0 {\displaystyle \Delta _{1}^{0}} , Σ Σ 1 0 {\displaystyle \Sigma _{1}^{0}} , and Π Π 1 0 {\displaystyle \Pi _{1}^{0}} levels of the arithmetical hierarchy, this means that Δ Δ 2 0 {\displaystyle \Delta _{2}^{0}} is the lowest level in the arithmetical hierarchy where random sequences can be found.

◀ Prev · Parts · Full · Next ▶